package sjjg.graph;

import sjjg.tree.MinPriorityQueue;
import sjjg.uf.UF_Tree_Weight;

import java.util.Queue;
import java.util.concurrent.LinkedBlockingQueue;

public class KruskalMST {
    private Queue<Edge>mst;//用来存储最小生成树的所有边
    private UF_Tree_Weight ufTreeWeight;//并查集 用来存储结点的相通性
    private MinPriorityQueue<Edge>minPriorityQueue;//存储加权无向图的所有边
    public KruskalMST(EdgeWeightGraph weightGraph){
           mst=new LinkedBlockingQueue<>();
           ufTreeWeight=new UF_Tree_Weight(weightGraph.V());
           minPriorityQueue=new MinPriorityQueue<>(weightGraph.E());//索引0废弃
           //将图中所有边入最小优先队列
        for (Edge edge : weightGraph.edges()) {
             minPriorityQueue.insert(edge);
        }
        while (!minPriorityQueue.isEmpty()&&mst.size()<weightGraph.V()-1){
            Edge edge = minPriorityQueue.delMin();//拿到队列中的最小边
            int v = edge.either();
            int w = edge.another(v);
            if(ufTreeWeight.connected(v,w)){//如果v w 在同一组就不能再添加这条边了 不然得到的就不是最小生成树了
                continue;
            }
            ufTreeWeight.union(v,w);//并入同一组
            mst.add(edge);//加入到mst中
        }
    }
    public Queue<Edge>edges(){
         return mst;
    }
}
